1) Field of the Invention
The present invention relates to a branch predicting apparatus and a branch predicting method that perform branch prediction in a processor of a pipeline system. In particular, the present invention relates to a branch predicting apparatus and a branch predicting method that can keep accuracy of a branch prediction high when plural call instructions are detected by a branch history prior to completion of execution of a call instruction.
2) Description of the Related Art
Conventionally, a method of branch prediction is widely used for speed-up of processing in a processor of a pipeline system. When a branch is present in a program, it is essentially necessary to stop a pipeline until the branch is defined. However, a processor for performing branch prediction predicts a branch and executes an instruction after the predicted branch speculatively.
The branch prediction has a significant advantage that, when a prediction comes true, it is possible to reduce processing time equivalent to time for waiting for a branch to be defined. However, when the prediction does not come true, since it is necessary to flush a pipeline and re-execute processing from a part where a branch instruction is given, the branch prediction also has a significant penalty. Therefore, accuracy of prediction is very important in the branch prediction.
In general, a branch history is used in the branch prediction. The branch history is a device that holds an address of a branch instruction executed in the past and an address of a branch destination branched by the branch instruction as a pair. Since the branch prediction using the branch history is based on a history in the past, the branch prediction is very effective when the same branch is repeated as in loop processing. However, the branch prediction is less effective for a branch according to a return instruction from a subroutine.
When a branch occurs according to the return instruction from the subroutine, a branch destination is an instruction next to a call instruction of the subroutine. However, in general, since the subroutine is called from various sections of a program, a return destination of the return instruction is not fixed. Therefore, even if the branch destination is predicted according to a history in the past, the prediction is not always correct.
Thus, in a method widely adopted, an address of a return destination according to a return instruction is stored in a return address stack when a call instruction of a subroutine is executed and, concerning the return instruction, branch prediction is performed for the return address stack preferentially over a branch history, whereby accuracy of a prediction is improved.
After the execution of the call instruction is completed, the return address stack stores an address of a return destination of a return instruction corresponding to the call instruction. Therefore, when the return instruction is detected by the branch history because of read-ahead or the like of an instruction stream before the execution of the call instruction is completed, there is a problem in that the address of the return destination is not stored in the return address stack and accuracy of branch prediction falls.
Thus, in Japanese Patent Application No. 2004-222399, the inventor proposes a technique for realizing highly accurate branch prediction even in the case described above by providing a second return address stack and storing an address of a return destination of a return instruction in a second return address stack at a stage when a call instruction is detected by a branch history.
However, the technique proposed in the above literature has a problem in that it is not taken into account that, after a call instruction is detected by the branch history, another call instruction is detected by the branch history until the execution of the call instruction is completed. Only one entry for storing an address of a return destination of a return instruction is provided in the second return address stack. Thus, when there are plural call instructions that have been detected by the branch history but execution of which has not been completed, addresses other than an address of a return destination of a return instruction corresponding to a call instruction detected last are discarded and accuracy of prediction of a branch destination falls.